package com.learn.algorithm.exercises.nowcoder;

import sun.reflect.generics.tree.Tree;

import java.util.HashMap;

/**
 * 给定一个字符串,为每一个字符串找出能够唯一识别该字符串的最小前缀
 *
 * @author wangxing
 * @version 2020/5/17 13:01 Administrator
 */
public class StringMinPrefix {
    public static String[] getStringMinPrefix(String[] arrStr) {
        int l = arrStr.length;
        String[] minPrefix = new String[l];
        PrefixTree tree = new PrefixTree();
        for (int i = 0; i < l; i++) {
            tree.insert(arrStr[i]);
        }
        for (int i = 0; i < l; i++) {
            minPrefix[i] = tree.findMaxPrefix(arrStr[i]);
        }
        return minPrefix;
    }

    /**
     * 前缀树
     */
    static class PrefixTree {
        class TreeNode {
            /**
             * 表示当前字符被多少个字符串公用
             */
            int path;
            /**
             * 表示多少个字符串以当前字符为结尾
             */
            int end;
            /**
             * 记录字符路径指向的节点
             */
            HashMap<Character, TreeNode> map;

            public TreeNode() {
                this.path = 0;
                this.end = 0;
                this.map = new HashMap<>();
            }
        }

        private TreeNode root;

        public PrefixTree() {
            root = new TreeNode();
        }

        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] cArr = word.toCharArray();
            TreeNode node = root;
            for (int i = 0, length = cArr.length; i < length; i++) {
                //判断当前字符是否在前缀树节点中,不存在就创建新的节点
                if (!node.map.containsKey(cArr[i])) {
                    node.map.put(cArr[i], new TreeNode());
                }
                //获取当前字符对应的前缀树节点
                node = node.map.get(cArr[i]);
                //给当前字符对应的前缀树节点的引用字符串数量加一
                node.path++;
            }
            //设置以当前节点为尾部节点的字符串数量加一
            node.end++;
        }

        public String findMaxPrefix(String word) {
            if (word.isEmpty()) {
                return "";
            }
            TreeNode node = root;
            String res = "";
            char[] chs = word.toCharArray();
            for (int i = 0; i < chs.length; i++) {
                if (node.map.containsKey(chs[i])) {
                    node = node.map.get(chs[i]);
                    res += chs[i];
                    if (node.path == 1) {
                        return res;
                    }
                } else {
                    return "";
                }
            }
            return res;
        }
    }
}
